class Solution
{
public:
    vector<int> findOriginalArray(vector<int> &changed)
    {
        int n = changed.size();
        if (n & 1)
        {
            return {};
        }
        sort(changed.begin(), changed.end());

        vector<int> origin;
        priority_queue<int> pq;
        for (int i = n - 1; i >= 0; --i)
        {
            if (pq.empty() || pq.top() != 2 * changed[i])
            {
                pq.push(changed[i]);
            }
            else
            {
                origin.push_back(changed[i]);
                pq.pop();
            }
        }
        if (!pq.empty())
        {
            return {};
        }

        return origin;
    }

    vector<int> findOriginalArray(vector<int> &changed)
    {
        int n = changed.size();
        if (n & 1)
        {
            return vector<int>();
        }
        n = n >> 1;
        vector<int> origin;
        origin.reserve(n);
        sort(changed.begin(), changed.end());

        // 原数列与其双倍元素的顺序是一致的，利用队列遍历一遍即可
        queue<int> q;
        for (auto it = changed.rbegin(); it != changed.rend(); ++it)
        {
            if (q.empty())
            {
                int maxNum = *it;

                // if (maxNum & 1)
                // {
                //     return vector<int>();
                // }
                // if (!maxNum)
                // {
                //     int zeroCount = (changed.rend() - it) / 2;
                //     for (int i = 0; i < zeroCount; ++i)
                //     {
                //         origin.push_back(0);
                //     }
                //     return origin;
                // } // max=0的这个trick就不必了，都是O(n)

                q.push(maxNum);
            }
            else
            {
                // 继续使用之前关于最大值的一些tricks
                if (q.front() & 1)
                {
                    return vector<int>();
                }
                if (q.front() >> 1 == *it)
                {
                    q.pop();
                    origin.push_back(*it);
                }
                else
                {
                    q.push(*it);
                }
            }
        }
        if (!q.empty())
        {
            return vector<int>();
        }
        return origin;
    }

private:
    // 用到了二分查找。用到了vector的删除操作，比较费时间
    vector<int> binarySearch(vector<int> &changed)
    {
        int n = changed.size();
        if (n & 1)
        {
            return vector<int>();
        }
        n = n >> 1;
        vector<int> origin;
        origin.reserve(n);
        sort(changed.begin(), changed.end());
        // 官方题解找最小的数，这里找的是最大的数
        // 如果最大的数是奇数，可以直接否决
        while (!changed.empty())
        {
            int maxNum = changed.back();
            if (maxNum & 1)
            {
                return vector<int>();
            }
            if (!maxNum)
            {
                // 剩下的数为全0时可以直接填入并返回
                // 对某些测试用例尤为有效
                int zeroCount = changed.size() / 2;
                for (int i = 0; i < zeroCount; ++i)
                {
                    origin.push_back(0);
                }
                return origin;
            }
            int halfMax = maxNum >> 1;
            changed.pop_back();
            auto halfIt = lower_bound(changed.begin(), changed.end(), halfMax);
            if (halfIt == changed.end() || *halfIt != halfMax)
            {
                return vector<int>();
            }
            origin.push_back(halfMax);
            changed.erase(halfIt);
        }
        return origin;
    }
};